/**
 * @Author Fizz Pu
 * @Date 2020/9/1 下午5:27
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.*;

/**
 * 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，
 * 并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
 * 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/satisfiability-of-equality-equations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

// 先构建等于关系的集合
// 然后验证不等于的关系

import java.util.HashMap;
import java.util.HashSet;

public class Lee990 {
        public  boolean equationsPossible(String[] equations) {
            UnionSearchSet unionSearchSet = new UnionSearchSet(getVar(equations));
            for(String equation: equations) {
                if (equation.charAt(1) == '=') {
                    char ele1 = equation.charAt(0);
                    char ele2 = equation.charAt(3);
                    unionSearchSet.union(ele1, ele2);
                }
            }

            for(String equation: equations) {
                if (equation.charAt(1) == '!' && unionSearchSet.sameSet(equation.charAt(0), equation.charAt(3))) {
                    return  false;
                }
            }
            return true;
            // error code
            /*switch (equation.charAt(1)) {
                    case '!' -> {
                        // 看是否矛盾了
                        // 变量之间存在关系,两个变量属于同一个集合
                        if (unionSearchSet.sameSet(ele1, ele2)) return false;
                    }
                    case '=' -> {
                        // 合并即可
                        unionSearchSet.union(ele1, ele2);
                    }
            }*/

        }

        // 获得变量
        HashSet<Character> getVar(String[] equations){
            HashSet<Character> variable = new HashSet<>();
            for(String equation : equations){
                variable.add(equation.charAt(0));
                variable.add(equation.charAt(3));
            }
            return  variable;
        }

}

// 自定义并查集
class UnionSearchSet {
    private HashMap<Character,Character> roots;

    // 初始化时，用hashmap存储父节点
    public UnionSearchSet(HashSet<Character> hashSet) {
        roots = new HashMap<>(hashSet.size());
        var iterator = hashSet.iterator();
        while (iterator.hasNext()){
            // roots.put(iterator.next(),iterator.next()); watch out! 使用迭代器時，不要調用next()兩次
            Character ele = iterator.next();
            roots.put(ele,ele);
        }
    }

    // 合并
    public void union(Character ele1, Character ele2) {
        Character x = find(ele1);
        Character y = find(ele2);
        if (x != y) { // 不是同一个集合就合并
            roots.put(x, y); // 相当于x的父亲是y
        }
    }

    // 查找
    // 利用路径压缩优化查找算法
    public Character find(Character element) {
        if (element.equals(roots.get(element))) {
            return element;
        }
        Character father = find(roots.get(element));
        roots.put(element,father);
        return father;
    }

    // 判断是否属于同于集合
    public boolean sameSet(Character ele1, Character ele2){
        return find(ele1).equals(find(ele2));
    }
}

